package 单调栈;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class LeetCode496_下一个更大元素 {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        Stack<Integer> st = new Stack<Integer>();
        int[] result = new int[nums1.length];

        for(int i = 0; i < nums2.length; i++) {
            while(!st.isEmpty() && st.peek() < nums2[i]) {
                // 栈不为空，栈顶元素为之前的值，后面来的值大于他且是第一个大于他的
                map.put(st.pop(),nums2[i]);
            }
            st.push(nums2[i]);
        }

        // 走到这里如果单调栈还不为空说明剩下的元素没有下一个比他更大的元素
        while(!st.isEmpty()) {
            map.put(st.pop(),-1);
        }

        for(int i = 0; i < nums1.length;i++) {
            result[i] = map.get(nums1[i]);
        }

        return result;
    }


}
